package com.zhanghp.class037;

import com.zhanghp.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 收集累加和等于aim的所有路径<br/>
 * 测试链接 : https://leetcode.cn/problems/path-sum-ii/
 *
 * @author zhanghp
 * @since 2024/4/19 15:24
 */
public class Code03_PathSumII {

    static class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            List<Integer> paths = new ArrayList<>();
            f(root, paths, 0, targetSum, ans);
            return ans;
        }

        public void f(TreeNode cur, List<Integer> paths, int pathSum, int targeSum, List<List<Integer>> ans) {
            // 默认添加现在的路径
            paths.add(cur.val);
            // 默认添加此节点的值，累和
            pathSum += cur.val;
            // 叶子结点
            if (cur.left == null && cur.right == null) {
                //则判断pathSum和targetSum是否相等
                if (pathSum == targeSum) {
                    paths.add(cur.val);
                    ans.add(copy(paths));
                    paths.remove(paths.size() - 1);
                }
            } else {
                // 非叶子结点
                // 左处理
                if (cur.left != null) {
                    f(cur.left, paths, pathSum, targeSum, ans);
                }
                // 右处理
                if (cur.right != null) {
                    f(cur.right, paths, pathSum, targeSum, ans);
                }
            }
            // 返回上一节点，便于上一节点路径处理
            // 如：左节点处理完了，那么返回节点，右节点还没处理，那么paths需要删除左节点的值
            // 如：右节点处理完了，返回上一级B，上一级在返回上一级A,A在处理另一个孩子
            paths.remove(paths.size() - 1);
        }

        public List<Integer> copy(List<Integer> paths) {
            List<Integer> ans = new ArrayList<>();
            for (Integer it : paths) {
                ans.add(it);
            }
            return ans;
        }
    }
}
